# coding=utf-8
# Date: 2021/9/12 11:02


# 执行用时：32 ms, 在所有 Python3 提交中击败了69.71%的用户
# 内存消耗：14.7 MB, 在所有 Python3 提交中击败了97.59%的用户
class Solution:
    def checkValidString(self, s: str) -> bool:
        low, high = 0, 0
        for c in s:
            if c == '(':
                low += 1
                high += 1
            elif c == ')':
                low -= 1
                high -= 1
            else:
                low -= 1
                high += 1
            low = max(low, 0)
            if low > high:
                return False
        return low == 0


if __name__ == "__main__":
    print(Solution().checkValidString("()"))  # True
